package com.example.Arithmetic.Lettcode;

import com.example.Arithmetic.Arithmetic.TreeNode;

/**
 * 日期：2023/10/18
 * 时间：9:20
 * 描述：根据前序遍历构造出一个二叉数
 */
public class E04Lettcode1008 {
    //    遍历递归方法
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode<>(preorder[0]);
        for (int i : preorder) {
            inster(root, i);
        }
        return root;
    }

    private TreeNode inster(TreeNode<Integer> root, int i) {
        if (root == null) {
            return new TreeNode(i);
        }
        if (root.val > i) {
            root.left = inster(root.left, i);
        }
        if (root.val < i) {
            root.right = inster(root.right, i);
        }
        return root;
    }

    //    上限方法
    public TreeNode bstFromPreorder1(int[] preorder) {
        return inst(preorder, Integer.MAX_VALUE);
    }

    int i = 0;

    private TreeNode inst(int[] preorder, int maxValue) {
        if (i == preorder.length || preorder[i] > maxValue) {
            return null;
        }
        TreeNode<Integer> node = new TreeNode(preorder[i]);
        i++;
        node.left = inst(preorder, node.val);
        node.right = inst(preorder, maxValue);
        return node;
    }

    //分治法
    public TreeNode bstFromPreorder3(int[] preorder) {
        TreeNode split = split(preorder, 0, preorder.length - 1);
        return split;
    }

    public TreeNode split(int[] p, int start, int end) {
        if (start > end) {
            return null;
        }
        TreeNode node = new TreeNode(p[start]);
        int index = start + 1;
        while (index <= end) {
            if (p[index] > p[start]) {
                break;
            }
            index++;
        }
        node.left = split(p, start + 1, index - 1);
        node.right = split(p, index, end);
        return node;
    }
}

